Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:

• A = [2,3,1,1,4], return true.
  
• A = [3,2,1,0,4], return false.

题目大意：给定一个数组，数组的每个值代表从当前位置可以走到的最长步数，判断是否可以到达终点

题目难度：Medium

/**
 * Created by gzdaijie on 16/5/26
 * step记录可以走到的地方,step > len - 1说明可以走到终点
 */
public class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) return true;

        int len = nums.length;
        int step = 0;

        for (int i = 0; i < len - 1; i++) {
            if (i > step) return false; // i超过step，说明无法到达step
            if (i + nums[i] > step) step = Math.max(i + nums[i], step); // 更新可以走到的最远位置
            if (step >= len - 1) return true; // 超过len - 1，说明可以到达终点
        }
        return false;
    }
}